Homework 5
Cellular automata
Cellular automata were invented in the 1950s by John von Neumann as formal models of
self-reproducing machines. The field was revived in the 1980s by Stephen Wolfram.
Wolfram is also the author of the program
Mathematica.
His early
papers
are available on his
web site.
He has spent the last nine years writing a new book on cellular automata. Titled
A New Kind of Science,
he believes it will revolutionize many fields. An interesting profile
God, Stephen Wolfram, and Everything Else by Michael S. Malone
was recently in Forbes ASAP.
5.1 One-dimensional cellular automata
Our cellular automata consist of a single-dimensional array of cells.
- Each cell can take on the value 0 or 1.
- Each time-step or generation all of the cells can take on a new value.
- The value of a cell at time T+1 is determined by the values of the cell and
its neighbors at time T.
- The transitions are specified in a transition table.
- Here is one based
on the sum of the values of the cell and its two nearest neighbors on each side:
| Sum |
Example |
New Value |
| 5 |
11111 |
0 |
| 4 |
11101 |
1 |
| 3 |
01101 |
0 |
| 2 |
10001 |
1 |
| 1 |
01000 |
0 |
| 0 |
00000 |
0 |
- Transition tables can be encoded into single numbers
above tables based on Introduction to Artificial Life, Christoph Adami, 1998
Based on their long-term behavior, Stephen Wolfram divided cellular automata rules
into four distinct classes.
- Class I - limit point behavior
- evolve to a homogeneous state (all zeros or all ones)
- example: code 60 rule
- Black represents value 1, white represents value 0.
- Generations/Time increases downwards.
- Class II - limit cycle behavior
- evolve periodic structures
- example: code 56 rule
- Class III - aperiodic, chaotic behavior
- example: code 10 rule
- Class IV - complex behavior
Wolfram is currently fascinated by class III rule 30
He sees this pattern in many areas of nature, such as pigmentation on
seashells. He believes cellular automata are the key to understanding how
simple rules produce complex structures and behavior.
Many other variations on cellular automata have been studied:
- Other types of transition tables can be used.
- Cells may take on more states than the simple 1/0 on/off.
- The automata may use two or more dimensions
- The most famous two-dimensional cellular automata is Conway's Life
5.2 Update rules in Python
Here's a Python function to calculate the new value of a cell, given the sum of the
cell and 2 nearest neighbors on each side, and the rule code:
def updateForSum(sum,rule):
mask = 1 << sum
if (rule & mask) != 0:
return 1
else:
return 0
You don't have to understand how this function works to use it, but here's an
explanation.
The rules codes can be represented as binary numbers instead of decimal.
- from the transition table above, rule code 20 becomes 010100
The function uses Python's bit-level operators << and &.
- << left shifts the value 1 as many times as the sum.
- & bitwise
ands the mask with the rule.
So the function reads the column of the transition table corresponding to
the sum passed in.
Yes, if you don't know binary arithmetic this explanation probably doesn't help.
Try
this site
and
this one
if you want to know more.
5.3 Cellular automata in Python
Your assignment is to write a program to display one-dimensional cellular automata.
- The program will repeatedly prompt the user for the rule code,
and generate the display.
First create a list with as many cells (elements) as your chosen screen width.
- Build it up from an empty list using the
append method from the
previous homework
- Initialize each cell with a random value 0 or 1.
To display the list in the window, iterate over each cell and use the
livewires plot function:
livewires.plot(x,y)
To calculate a new generation, first copy the list to a temporary list.
- For each cell in the temporary list sum its current value with that of its two
closest neighbors on each side, and call
updateForSum to determine the
new value.
- Be sure to handle the neighbor-does-not-exist cases (near the list ends).
The temporary list now becomes the current list.
- display the new current list one line down
- repeat for height of display window
During debugging you should use a small display (say 50x50). Generating 400x400
displays takes a LONG time in Python...
Don't forget to call livewires.clear_screen() when you start to
display a new code rule.
Also, the drawable area of the livewires display window appears to be a few pixels
shorter than the requested height. Try leaving a few blank lines at the top to
ensure you are displaying all the data (the first line should always look random).
When your program is working, try out different code rules. You may even find one
that impresses Stephen.
= 5
